package _11_整理题目._7_查找排序._0_二分查找;

import org.junit.Test;

/**
 * 给定一个长度为 n 的非降序数组和一个非负数整数 k ，
 * 要求统计 k 在数组中出现的次数.
 *
 * logn 分别查找左右边界，然后计算
 */
public class _04_计算非降序数组中某个数的数量 {

    public int GetNumberOfK(int[] array , int k) {
        if(array==null || array.length==0) return 0;
        int left = getIndex(array, k, true);
        int right = getIndex(array, k, false);
        if(left==-1 || right==-1) return 0;
        else return right - left + 1;
    }

    public int getIndex(int[] array, int target, boolean isLeft) {
        int left = 0, right = array.length-1;
        int index = -1;
        if (isLeft) {
            while (left <= right) {
                int mid = left + (right-left) / 2;
                if (array[mid] < target) {
                    left = mid + 1;
                } else if (array[mid] > target) {
                    right = mid - 1;
                } else {
                    right = mid - 1;
                }
            }
            if (left <array.length && array[left] == target) {
                index = left;
            }
        } else {
            while (left <= right) {
                int mid = left + (right-left) / 2;
                if (array[mid] < target) {
                    left = mid + 1;
                } else if (array[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            if (right >=0 && array[right] == target) {
                index = right;
            }
        }
        return index;
    }

    @Test
    public void main() {
        int[] nums = {1,2,3,3,3,3,4,5};
        System.out.println(GetNumberOfK(nums, 3));
    }
}
